Sorting Algorithms
Bubble Sort
Complexity:-
Time complexity(Best): O(n)
Time complexity(Worst): O(n ^ 2)
Space complexity: O(1)
1. Function Bubblesort(size , array[])
2. i = size
3. while ( i > 0 )
4. j = 0
5. while ( j < i )
6. if ( array[j] > array[j+1])
7. temp = array[j]
8. array[j] = array[j+1]
9. array[j+1] = temp
10. end if
11. j++
12. end while
13. i--
14. end while
15. end Bubblesort
Insertion Sort
Complexity:-
Time complexity(Best): O(n)
Time complexity(Worst): O(n ^ 2)
Space complexity: O(1)
1. Function Insertionsort(array[] , size)
2. i = 1
3. while( i < size )
4. temp = array[i]
5. j = i – 1
6. while( j >= 0 && array[j] > temp)
7. array[j+1] = array[j]
8. end while
9. array[j+1] = temp
10. end while
11. end insertionsort
Count Sort
Complexity:-
Time complexity(Best): O(n + k) where n is the number of elements and k is the range
Time complexity(Worst):O(n + k)
Space complexity:O(n + k)
1. Function Count_sort( array[] , size , low , range )
2. i = 0
3. count[] = {0 , range} // a temporary array used to sort element
4. while( i < size )
5. count[ array[i] – low] ++
6. i++
7. end while
8. j = 0
9. c = 0
10. while( j<range )
11. k = 0
12. while( k<count[j] )
13. array[c] = j + low
14. c++
15. end while
16. end while
17. End Count_sort
Quick Sort
Complexity:-
Time complexity(Best):O(n * log(n))
Time complexity(Worst):O(n ^ 2)
Space complexity:O(n)
1. Function quicksort(begin , end , array[])
2. pivot = array[(begin+end)/2]
3. i = begin
4. j= end
5. while( i <= j )
6. while(array[i] < pivot)
7. i++
8. end while
9. while(array[j] > pivot)
10. j--
11. end while
12. if (i <= j)
13. temp=array[i]
14. array[i]=array[j]
15. array[j]=temp
16. end if
17. if begin < j
18. quicksort(begin, j , array[]) /* recursive function to sort the first half of the array */
19. if end > i
20. quicksort(i ,end ,array[])
21. end while
22. end quicksort
Merge Sort
Complexity:-
Time complexity(Best): O(n * log(n))
Time complexity(Worst): O(n * log(n))
Space complexity: O(n)
1. Function merge_sort( array[] , begin , end ) //function which splits the array
2. mid = ( begin + end ) / 2 //initial value of begin is 0 and end is size-1
3. if( begin < end )
4. merge_sort( array[] , begin , mid )
5. merge_sort( array[] , mid+1 , end )
6. merge( array[] , begin , mid , end )
7. end if
8. end merge_sort
1. Function merge( array[] , begin , mid , end ) //function which sorts and merges the array
2. i = begin
3. j = begin
4. k = mid + 1
5. declare temp[]
6. while( i <= mid && k <= end )
7. if( array[i] < array[k] )
8. temp[j] = array[i]
9. i++
10. j++
11. end if
12. else
13. temp[j] = array[k]
14. k++
15. j++
16. end while
17. while( i<= mid )
18. temp[j] = array[i]
19. i++
20. j++
21. end while
22. while ( k <= end )
23. temp[j] = array[k]
24. k++
25. j++
26. end while
27. i = begin
28. while( i < k )
29. array[i] = temp[i]
30. i++
31. end while
32. end merge
